This invention relates to a method and apparatus for minimizing power signature attacks in cryptographic systems.
Cryptographic systems generally owe their security to the fact that a particular piece of information is kept secret without which it is almost impossible to break the scheme. The secret information must generally be stored within a secure boundary in the cryptographic processor, making it difficult for an attacker to get at it directly. However, various schemes or attacks have been attempted in order to obtain this secret information. One of these is the timing or power signature attack.
The timing attack (or xe2x80x9cside channel attackxe2x80x9d) is an obvious result of sequential computational operations performed during cryptographic operations. The attack usually exploits some implementation aspect of a cryptographic algorithm.
For example current public key cryptographic schemes such as RSA and elliptic curve (EC) operate over mathematical groups; Z*n(n=pq) in RSA, discrete log systems in a finite field F*q(q is a power of a prime), F*2M or an EC group over these finite fields. The group operations, called multiplication modulo n, in RSA, and addition of points in EC are sequentially repeated in a particular way to perform a scalar operation. In RSA the operand is called an exponent, the operation is called exponentiation and the method of multiplying is commonly known as repeated square-and-multiply. Thus given a number axcex5Z*n and an integer 0xe2x89xa6k less than p, the exponent, whose binary representation is k=xcexa31=0i ki 2i a value ak mod n may be calculated by repeated use of the xe2x80x9csquare-and-multiplyxe2x80x9d algorithm (described in Handbook of Applied Cryptography P.615). Similarly given g(x)xcex5Fpm and an integer 0xe2x89xa6kxe2x89xa6pmxe2x88x921 then g(x)k mod f(x) may be calculated by this method.
On the other hand, in EC the operand is a scalar multiplier, the operation is called scalar multiplication of a point, and the method is known as xe2x80x9cdouble-and-addxe2x80x9d. Thus if k is a positive integer and P is an elliptic curve point then kP may be obtained by the xe2x80x9cdouble-and-addxe2x80x9d method. Both these methods are well known in the art and will not be discussed further.
As mentioned earlier, an attacker once in possession of the private key (either long term or session) is able to forge signatures and decrypt secret messages for the attacked entity. Thus it is paramount to maintain the secrecy or integrity of the private key in the system.
Many techniques have been suggested to obtain the private key. The encryption operations are performed either in a special purpose or general-purpose processor operating in a sequential manner. Recent attack methods have been proposed in open literature as for example described in Paul Kochers""s article xe2x80x9cTiming attacks on implementations of Diffie-Hellman, RSA, DSS and other systemsxe2x80x9d. These attacks have been based on timing analysis of these processors or in other words timing analysis of xe2x80x98black boxxe2x80x99 operations. In one instance an attacker by capturing the instantaneous power usage of a processor throughout a private key operation obtains a power signature. The power signature relates to the number of gates operating at each clock cycle. Each fundamental operation as described in the preceding paragraph generates a distinct timing pattern. Other methods exist for obtaining a power signature than instantaneous power usage.
Laborious but careful analysis of an end-to-end waveform can decompose the order of add-and-double or square-and-multiply operations. Using the standard algorithm, either a double or square must occur for each bit of either the exponent or scalar multiplier respectively. Therefore, the places where double waveforms are adjacent each other represent bit positions with zeros and places where there are add waveforms indicate bits with ones. Thus, these timing measurements can be analyzed to find the entire secret key and thus compromise the system.
In addition to the xe2x80x9csquare and multiplyxe2x80x9d or xe2x80x9cdouble and addxe2x80x9d techniques mentioned earlier, other methods to compute kP are for example the xe2x80x9cbinary ladderxe2x80x9d or Montgomery method described in xe2x80x9cSpeeding the Pollard and Elliptic Curve Methods of Factorizationxe2x80x9d by Peter L. Montgomery. In this method the x-coordinates of the pair of points (iP, (i+1)P) are computed. The Montgomery method is an efficient algorithm for performing modula multiplication, more clearly illustrated by an example. Given a group E (Fp) and given a point P on the elliptic curve, the Montgomery method may be used to compute another point kP. Given an ordered pair of points (iP, (i+1)P), then for each of the bits of the binary representation of k, if bit i is a 0 then the next set of points computed is (2iP, (2i+1)P) and if bit i is 1, then the next set of points is ((2i+1)P, (2i+2)P), that is, the first of the pair is derived from a doubling or an adding depending on whether the bit is a 0 or 1.
In a processor, each of the doubles and adds involve multiple operations which generate unique power signatures. By observing these power signatures as shown schematically in FIG. 1(a), the attacker may derive a sequence of 0s and 1s and thus, the scalar or exponent being used.
The Montgomery method is preferable in EC cryptographic systems because of its extreme efficiency over the straight xe2x80x9cdouble and addxe2x80x9d described earlier.
The attack on the Montgomery method as described above is particularly important if performing RSA private key operations. In a recent paper published by Dan Boneh et al entitled xe2x80x9cAn Attack On RSA Given A Small Fraction Of The Private Key Bitsxe2x80x9d, it has been shown that for RSA with a low public exponent, given a quarter of the bits of the private key, an adversary can determine the entire private key. With this attack combined with the power signature attack described above, the RSA scheme is extremely vulnerable.
Thus, it is an object of this invention to provide a system which minimizes the risk of a successful timing attack particularly when utilizing the Montgomery method on private key operations.
In accordance with this invention, there is provided a method of computing a multiple k of a point P on an elliptic curve defined over a field, said method comprising the steps of:
a) representing the number k as binary vector of bits ki;
b) forming an ordered pair of points P1 and P2, wherein the points P1 and P2 differ at most by P; and
c) selecting each said bits ki in sequence; and for each of said ki;
i) upon ki being a 0
ii) computing a new set of points P1xe2x80x2, P2xe2x80x2 by doubling the first point P1 to generate said point P1xe2x80x2; and
iii) adding the points P1 and P2 to generate the point P2xe2x80x2; or upon ki being a 1
iv) computing a new set of points P1xe2x80x2, P2xe2x80x2 by doubling the second point P2 to generate the point P2xe2x80x2; and
v) adding the points P1 and P2 to produce the point P1xe2x80x2,
whereby said doubles or adds are always performed in the same order for each of said bits bi, thereby minimizing a timing attack on said method.
In accordance with a further aspect of this invention, the field is either F2m or Fp.
In accordance with a further aspect of this invention, there is provided a processor hardware for implementing the method.